package LeetCode.interview;

import util.LogUtils;

/*
 * 
 原题
 	Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. 
 题目大意
 	合并两个排序链表并返回一个新的列表。新的链表的结果由原先的两个链表结点组成，也就是不能合并后的链表不能包含新创建的结点。 
 解题思路
 	使用头结点root进行辅助操作，创建一个头结点，再使用两个引用指向两个链表的头结点，将较小的结点值的结点摘下来接到root链表的末尾，
 	同时被摘的链头引用移动到下一个结点，一直操作，到到原先两个链表中有一个为空，
 	最后再将剩下的结点接到root链表的末尾。最后返回root的下一个结点，其就为新的链表头。  
 @个人理解：类似于 原地归并排序
 * @Date 2017-09-12 17：46
 */
public class _021_Merge_Two_Sorted_Lists {
	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}

	private ListNode result = null;
	
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		if (l1==null && l2==null)	return null;
		if (l1==null || l2==null) {
			return l1 == null ? l2 : l1;
		}
		
		/**
		 * 尾插法
		 */
		//创建一个临时头结点，等会还要删掉
		ListNode root = new ListNode(0);
		ListNode tail = root;
		
		//与原地归并排序一样，两个节点比较，取较小的
		while (l1!=null && l2!=null) {
			if (l1.val < l2.val) {
				tail.next = l1;
				l1 = l1.next;
			} else if (l1.val > l2.val) {
				tail.next = l2;
				l2 = l2.next;
			} else {
				//两个链表随便取一个
				tail.next = new ListNode(l1.val);
				tail = tail.next;
				tail.next = new ListNode(l1.val);
				l1 = l1.next;
				l2 = l2.next;
			}
			tail = tail.next;				//移动到下一个节点
		}
		
		//当其中某一个链表取完后，将另外一个链表全部接到tail后
		tail.next = (l1==null ? l2 : l1);
		
		traverse(root.next);
		//删除头结点 (将root的后续节点返回)
		return root.next;
	}
	
	private void traverse(ListNode l) {
		while (l != null) {
			System.out.println(l.val+">>");
			l = l.next;
		}
	}
	
	private ListNode newLinkList1() {
		ListNode root = new ListNode(1);
		root.next = new ListNode(2);
		root.next.next = new ListNode(3);
		root.next.next.next = new ListNode(4);
		root.next.next.next.next = new ListNode(5);
		return root;
	}
	
	private ListNode newLinkList2() {
		ListNode root = new ListNode(7);
		root.next = new ListNode(8);
		root.next.next = new ListNode(9);
		root.next.next.next = new ListNode(10);
		root.next.next.next.next = new ListNode(11);
		return root;
	}
	
	public static void main(String[] args) {
		_021_Merge_Two_Sorted_Lists obj = new _021_Merge_Two_Sorted_Lists();
		obj.mergeTwoLists(obj.newLinkList1(), obj.newLinkList1());
	}
}
